UVa/11110 - Equidivisions/equi.cpp

   1 /*
   2
   3   Problem: 11110 - Equidivisions
   4
   5   Andrés Mejía-Posada
   6
   7  */
   8 #include <iostream>
   9 #include <string>
  10 #include <sstream>
  11
  12 using namespace std;
  13
  14 const int MAXN = 110;
  15
  16 int  n;
  17 int  g[MAXN+1][MAXN+1];
  18 bool v[MAXN+1][MAXN+1];
  19
  20 //Retorna el número de casillas visitadas empezando en la casilla (i,j) si es de color c.
  21 int dfs(int i, int j, int c){
  22   if ( (0 <= i && i < n && 0 <= j && j < n &&
  23         !v[i][j] && c == g[i][j]) == false )
  24     return 0;
  25   int ans = 1;
  26   v[i][j] = true;
  27   for (int di=-1; di<=1; ++di){
  28     for (int dj=-1; dj<=1; ++dj){
  29       if ((di == 0 || dj == 0) && (di != 0 || dj != 0) ){
  30         ans += dfs(i+di, j+dj, c);
  31       }
  32     }
  33   }
  34   return ans;
  35 }
  36
  37 bool todo_bien(){
  38   for (int color=0; color<n; ++color){
  39     for (int i=0; i<n; ++i){
  40       for (int j=0; j<n; ++j){
  41         if (g[i][j] == color && !v[i][j]){
  42           if (dfs(i, j, color) != n) return false;
  43         }
  44       }
  45     }
  46   }
  47   return true;
  48 }
  49
  50 int main(){
  51   while (cin >> n && n){
  52     string line;
  53     getline(cin, line);
  54     memset(g, 0, sizeof g);
  55     memset(v, 0, sizeof v);
  56     for (int i=1; i<n; ++i){
  57       //Leer la partición de color i.
  58       //La partición que no está indicada es de color 0.
  59
  60       getline(cin, line);
  61       stringstream sin(line);
  62       int r, c;
  63       while (sin >> r >> c) g[--r][--c] = i;
  64     }
  65
  66     cout << (todo_bien() ? "good" : "wrong") << endl;
  67   }
  68   return 0;
  69 }